package com.ufo.algorithm.sorting;

import edu.princeton.cs.algs4.StdOut;

public class InsertSortV2 extends Sort {
    //2.1.25优化插入排序，将较大元素右移而非交换（不使用exch）
    public void sort(Comparable[] a){
        int len = a.length;
        Comparable temp;//记录被右移挤掉的元素
        for (int i=1;i<len;i++){
            int j=i;
            temp=a[j];
            for (;j>0 && less(temp, a[j-1]);j--){
                a[j]=a[j-1];//左侧元素不断右移
            }
            a[j]=temp;
        }
    }

    public static void main(String[] args){
        InsertSortV2 a=new InsertSortV2();
        Integer[] data= {4,3,2,5,1,7};
        a.sort(data);
        a.show(data);
    }
}
